// https://leetcode.cn/problems/restore-ip-addresses/
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    int len;
    vector <string> res;

    vector <string> restoreIpAddresses(string s) {
        len = s.size();
        if (len <= 3 || len >= 13) return {};
        for (int i = 1; i <= 3; i++) {
            dfs(s, "", 1, 0, i);
        }

        return res;
    }

    /**
     *
     * @param tmpS string 临时字符串
     * @param index
     * @param left
     * @param offset
     */
    void back(string &s, string tmpS, int index, int left, int offset) {
        string tmp = s.substr(left, offset);
        if(tmp.size() > 1 && tmp[0] == '0') return;
        if (stoi(tmp, nullptr, 0) > 255) return;
        tmpS = tmpS + "." + tmp;
        if (index == 4) {
            res.push_back(tmpS.substr(1, len + 3)); // len - 1 + 3
            return;
        }
        left = left + offset;
        if (index < 3) {
            for (int i = 1; i < 4; i++) {
                if (len - left - i > (4 - index) * 3 || len - left - i <= 0) continue;
                dfs(s, tmpS, index + 1, left, i);
            }
        } else {
            dfs(s, tmpS, index + 1, left, len - left);
        }
    }

};


int main() {
    Solution so;
//    string s = "25525511135"; // 11
    string s = "0000"; // 11
    cout << s << endl;
    vector <string> res = so.restoreIpAddresses(s);
    for (auto i : res) {
        cout << i << endl;
    }
    return 0;
}